"""
!!!important!!!
2576. 求出最多标记下标
已解答
中等
相关标签
相关企业
提示
给你一个下标从 0 开始的整数数组 nums 。

一开始，所有下标都没有被标记。你可以执行以下操作任意次：

选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。
请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。



示例 1：

输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。
示例 2：

输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。
示例 3：

输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。


提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
"""


class Solution(object):
    def maxNumOfMarkedIndices_res(self, nums) -> int:
        nums.sort()
        left, right = 0, len(nums) // 2 + 1  # 开区间
        while left + 1 < right:
            k = (left + right) // 2
            if all(nums[i] * 2 <= nums[i - k] for i in range(k)):
                left = k
            else:
                right = k
        return left * 2  # 最多匹配 left 对，有 left * 2 个数

    def maxNumOfMarkedIndices(self, nums):
        nums.sort()
        length = len(nums)
        l = 0
        r = length//2 + 1
        while l + 1 < r:
            mid = (l + r)//2
            if self.check(nums,mid):
                l = mid
            else:
                r = mid
        return l * 2


    def check(self,nums,l):
        i = 0
        length = len(nums)
        while i<l:
            if nums[i] * 2 <= nums[length + i - l]:
                i+=1
            else:
                return False
        return True


    def maxNumOfMarkedIndices_Err1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        记录l和r,每次找到r刚好大于l两倍的，同时记录l的最小数字m,如果l到m且r不是最后一个数字，则m++,r++
        """
        nums.sort()
        l = 0
        length = len(nums)
        r = length - 1
        if nums[l] * 2 > nums[r]:
            return 0
        while l < r:
            if nums[l+1] * 2 <= nums[length-1] and nums[0] * 2 <= nums[r-1]:
                l += 1
                r -= 1
            else:
                break
        return (l + 1) * 2


if __name__ == '__main__':
    s = Solution()
    print(s.maxNumOfMarkedIndices([3, 5, 2, 4])) #2
    print(s.maxNumOfMarkedIndices([9, 2, 5, 4])) #4
    print(s.maxNumOfMarkedIndices([7, 6, 8])) #0
